package HighMethod05;

/**
 * ClassName:    test
 * Package:    HighMethod05
 * Description: 红黑树 可以和高度平衡数对比
 * Datetime:    2021/4/17 0017   19:24
 * Author: 沈新源
 */
class RBTree {
    enum ColorType {RED, BLACK}

    ;

    class rb_node {
        rb_node leftchild;
        rb_node parent;
        rb_node rightchild;
        ColorType color; // RED  BLACK 要么是红色要么是黑色
        int key;

        public rb_node() {
            leftchild = parent = rightchild = null;
            color = ColorType.RED;
            key = 0;
        }

        public rb_node(int kx) {
            super();        //调用上一个无参的构造函数
            //继承下：在子类的构造方法中，只要里面没有显示的通过super去调用父类相应的构造方法，默认都是调用super()，即无参构造方法，因此要确保父类有相应的构造方法。
            //再次同样要保证有无参的构造函数
            key = kx;
        }
    }

    rb_node root;
    rb_node nil;    //哨兵节点

    public RBTree() {
        root = null;
        nil = new rb_node();
        nil.color = ColorType.BLACK;
    }

    private void RotateLeft(rb_node ptr) {
        rb_node newroot = ptr.rightchild;
        newroot.parent = ptr.parent;//1
        ptr.rightchild = newroot.leftchild;
        if (newroot.leftchild != null) {
            newroot.leftchild.parent = ptr;//2
        }
        newroot.leftchild = ptr;
        rb_node pa = ptr.parent;
        if (pa == null) {
            root = newroot;
        } else {
            if (pa.leftchild == ptr) {
                pa.leftchild = newroot;
            } else {
                pa.rightchild = newroot;
            }
        }
        ptr.parent = newroot; // 3
    }

    private void RotateRight(rb_node ptr) {
        rb_node newroot = ptr.leftchild;
        newroot.parent = ptr.parent; //1
        ptr.leftchild = newroot.rightchild;
        if (newroot.rightchild != null) {
            newroot.rightchild.parent = ptr;
        }
        newroot.rightchild = ptr;
        rb_node pa = ptr.parent;
        if (pa == null) {
            root = newroot;
        } else {
            if (pa.leftchild == ptr) {
                pa.leftchild = newroot;
            } else {
                pa.rightchild = newroot;
            }
        }
        ptr.parent = newroot;
    }

    //调整红黑树 比高度平衡树要简单多了（^~^）
    void Adjust(rb_node p) {
        //p的双亲不为空，且p双亲是红色
        while (p.parent != null && p.parent.color == ColorType.RED) {
            //判断p在双亲的双亲的右边
            if (p.parent.parent.rightchild == p.parent)// rigthchild
            {
                rb_node left = p.parent.parent.leftchild;
                if (left.color == ColorType.RED) {  //如果双亲的双亲的左节点是红色，仅调整颜色即可
                    p.parent.color = ColorType.BLACK;
                    left.color = ColorType.BLACK;
                    p.parent.parent.color = ColorType.RED;
                    p = p.parent.parent;        //p 指向双亲的双亲，下躺循环时退出
                } else {    //如果双亲的双亲的左节点是黑色（哨兵位是黑色），变换颜色后需要左旋
                    if (p.parent.leftchild == p) {  //如果是双亲的左节点，先右旋调整
                        p = p.parent;
                        RotateRight(p);
                    }
                    p.parent.color = ColorType.BLACK;       //下次循环也刚好退出
                    p.parent.parent.color = ColorType.RED;  //调整颜色
                    RotateLeft(p.parent.parent);        //左旋完成最终调整
                }
            } else {// leftchild  否则p在双亲的双亲的左边  与以上类似

                rb_node right = p.parent.parent.rightchild;
                if (right.color == ColorType.RED) { //如果双亲的双亲的右节点是红色，仅调整颜色即可
                    p.parent.color = ColorType.BLACK;
                    right.color = ColorType.BLACK;
                    p.parent.parent.color = ColorType.RED;
                    p = p.parent.parent;
                } else {
                    if (p.parent.rightchild == p) {
                        p = p.parent;
                        RotateLeft(p);
                    }
                    p.parent.color = ColorType.BLACK;
                    p.parent.parent.color = ColorType.RED;
                    RotateRight(p.parent.parent);
                }
            }
        }

    }

    //向红黑树插入一个节点
    boolean Insert_Item(int kx) {
        // BST;

        rb_node p = new rb_node();
        p.key = kx;
        p.leftchild = p.rightchild = nil;
        Adjust(p);
        return true;
    }

}

/**
 * 还没有测试。。
 */
public class test {
    public static void main(String[] args) {
        int[] ar = {53, 17, 78, 9, 45, 65, 87, 23, 81, 94, 88, 92};
/**                     53
 *              17               87
 *          9       45       65       92
 *                23           81   88  94
 *                            78
 *
 */
        RBTree rbTree = new RBTree();
        System.out.println("创建AVL树-------！");
        for (int i = 0; i < ar.length; i++) {
            rbTree.Insert_Item(ar[i]);
        }
        System.out.println();
    }
}
